package com.yun.algorithm.divideandconquer.leetcode;

public class LongestSubstringLeetcode395 {
    public int longestSubstring(String s, int k) {
        char[] c=s.toCharArray();
        return longestSubChar(c,0,c.length-1,k);
    }

    private int longestSubChar(char[] c,int left,int right,int k){
        if(right-left+1<k){
            return 0;
        }
        //利用计数排序的思想统计每个字符出现的次数
        int[] map=new int[26];
        for (int i = left; i <= right; i++) {
            map[c[i]-'a']++;
        }
        /*
            1.将该字符串进行分段,如果某个字符出现的次数小于K,说明其不可能满足题目要求的字符串
            2.遍历时需要一个max变量来记录分段后,其中最长子串的长度
            3.使用一个prev变量来记录上一段分段的起点
            4.使用一个notLongest来判断这一个分段是否出现出现次数小于K的字符,如果没出现则返回该分
            段长度.如果出现,则说明最后一段还未处理.

         */
        int max=0;
        int prev=left;
        boolean notLongest=false;
        for (int i = left; i <= right; i++) {
            if(map[c[i]-'a']<k){
                if(max<i-prev){
                    max=Math.max(max,longestSubChar(c,prev,i-1,k));
                }
                prev=i+1;
                notLongest=true;
            }
        }
        if(notLongest){
            if(max<right-prev+1){
                max=Math.max(max,longestSubChar(c,prev,right,k));
            }
        }else {
            return right-left+1;
        }
        return max;
    }

    public static void main(String[] args) {
        String s="aaabb";
        int k=3;
        System.out.println(new LongestSubstringLeetcode395().longestSubstring(s,k));
    }
}
